package jianzhioffer

import (
	"regexp"
	"sort"
	"strings"
)

type ListNode struct {
	Val  int
	Next *ListNode
}

//剑指 Offer II 001. 整数除法
func divide(a int, b int) int {
	sign := 1
	if a < 0 {
		sign = -sign
		a = -a
	}
	if b < 0 {
		sign = -sign
		b = -b
	}
	res := 0
	for a >= b {
		val := b
		cnt := 1
		for val <= a {
			if val<<1 > a {
				break
			}
			cnt = cnt << 1
			val = val << 1
		}
		res += cnt
		a -= val
	}
	res *= sign
	if res > 2147483647 || res < (-2147483648) {
		res = 2147483647
	}
	return res
}

//剑指 Offer II 002. 二进制加法
func addBinary(a string, b string) string {
	if len(a) < len(b) {
		a, b = b, a
	}
	for i := len(a) - len(b); i > 0; i-- {
		b = "0" + b
	}
	var res string
	carry := byte(0)
	for i := len(a) - 1; i >= 0; i-- {
		tmp := (a[i] - '0') + (b[i] - '0') + carry
		carry = 0
		if tmp>>1 > 0 {
			carry = tmp >> 1
			tmp = tmp % 2
		}
		res = string(tmp+'0') + res
	}
	if carry > 0 {
		res = string(carry+'0') + res
	}
	return res
}

//剑指 Offer II 003. 前 n 个数字二进制中 1 的个数
func countBits(n int) []int {
	res := []int{0}
	for i := 1; i <= n; i++ {
		cnt := 0
		tmp := i
		for tmp > 0 {
			tmp = tmp & (tmp - 1)
			cnt++
		}
		res = append(res, cnt)
	}
	return res
}

//剑指 Offer II 006. 排序数组中两个数字之和
func twoSum(numbers []int, target int) []int {
	left, right := 0, len(numbers)-1
	for left < right {
		tmp := numbers[left] + numbers[right]
		if tmp < target {
			left++
		} else if tmp > target {
			right--
		} else {
			break
		}
	}
	return []int{left, right}
}

//剑指 Offer II 007. 数组中和为 0 的三个数
func threeSum(nums []int) [][]int {
	var left, right int
	sort.Ints(nums)
	res := [][]int{}
	for i := 0; i < len(nums)-2; i++ {
		left, right = i+1, len(nums)-1
		for left < right {
			tmp := nums[i] + nums[left] + nums[right]
			if tmp == 0 {
				res = append(res, []int{nums[i], nums[left], nums[right]})
				for left+1 < right && nums[left] == nums[left+1] {
					left++
				}
				for left < right-1 && nums[right] == nums[right-1] {
					right--
				}
				left++
				right--
			} else if tmp < 0 {
				left++
			} else {
				right--
			}
		}
		for i+1 < len(nums)-2 && nums[i] == nums[i+1] {
			i++
		}
	}
	return res
}

//剑指 Offer II 012. 左右两边子数组的和相等
func pivotIndex(nums []int) int {
	dp := make([]int, len(nums))
	dp[0] = nums[0]
	for i := 1; i < len(nums); i++ {
		dp[i] = dp[i-1] + nums[i]
	}
	if dp[len(dp)-1]-dp[0] == 0 {
		return 0
	}
	for i := 1; i < len(dp); i++ {
		if dp[i-1] == dp[len(dp)-1]-dp[i] {
			return i
		}
	}
	return -1
}

type NumMatrix struct {
	matr [][]int
}

func Constructor(matrix [][]int) NumMatrix {
	m, n := len(matrix), len(matrix[0])
	res := NumMatrix{
		matr: make([][]int, m),
	}
	for i := range res.matr {
		res.matr[i] = make([]int, n)
	}
	for i := 0; i < m; i++ {
		res.matr[i][0] = matrix[i][0]
		for j := 1; j < n; j++ {
			res.matr[i][j] = matrix[i][j] + res.matr[i][j-1]
		}
	}
	return NumMatrix{matrix}
}

func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
	var sum int
	for i := row1; i <= row2; i++ {
		if col1 == 0 {
			sum += this.matr[i][col2]
		} else {
			sum += this.matr[i][col2] - this.matr[i][col1-1]
		}
	}
	return sum
}

//剑指 Offer II 014. 字符串中的变位词
func checkInclusion(s1 string, s2 string) bool {
	if len(s2) < len(s1) {
		return false
	}
	ch1, ch2 := [26]int{}, [26]int{}
	for i := range s1 {
		ch1[s1[i]-'a']++
		ch2[s2[i]-'a']++
	}
	for i := 0; i <= len(s2)-len(s1); i++ {
		if ch1 == ch2 {
			return true
		}
		ch2[s2[i]-'a']--
		if i != len(s2)-len(s1) {
			ch2[s2[i+len(s1)]-'a']++
		}
	}
	return false
}

//剑指 Offer II 018. 有效的回文
func isPalindrome(s string) bool {
	s = strings.ToLower(s)
	reg := regexp.MustCompile("[0-9A-Za-z]")
	ss := reg.FindAllString(s, -1)
	for i := 0; i < len(ss)/2; i++ {
		if ss[i] != ss[len(ss)-1-i] {
			return false
		}
	}
	return true
}

//剑指 Offer II 019. 最多删除一个字符得到回文
func validPalindrome(s string) bool {
	left, right := 0, len(s)-1
	f := func(s string) bool {
		left, right := 0, len(s)-1
		for left < right {
			if s[left] != s[right] {
				return false
			}
			left++
			right--
		}
		return true
	}
	for left < right {
		if s[left] != s[right] {
			return f(s[left+1:right+1]) || f(s[left:right])
		}
		left++
		right--
	}
	return true
}

//剑指 Offer II 024. 反转链表
func reverseList(head *ListNode) *ListNode {
	var pre *ListNode
	node := head
	for node != nil {
		tmp := node.Next
		node.Next = pre

		pre = node
		node = tmp
	}
	return pre
}

func getIntersectionNode(headA, headB *ListNode) *ListNode {
	h1, h2 := headA, headB
	diff := 0
	for h1 != nil && h2 != nil {
		h1 = h1.Next
		h2 = h2.Next
	}
	for h1 != nil {
		h1 = h1.Next
		diff++
	}
	for h2 != nil {
		h2 = h2.Next
		diff--
	}
	h3, h4 := headA, headB
	for h3 != nil && h4 != nil {
		if diff > 0 {
			h3 = h3.Next
			diff--
		} else if diff < 0 {
			h4 = h4.Next
			diff++
		} else {
			if h3 == h4 {
				return h3
			}
			h3 = h3.Next
			h4 = h4.Next
		}
	}
	return nil
}

type MovingAverage struct {
	count    int
	size     int
	last_avg float64
	array    []int
}

/** Initialize your data structure here. */
func Constructor(size int) MovingAverage {
	return MovingAverage{
		count:    0,
		size:     size,
		last_avg: 0,
		array:    make([]int, size),
	}
}

func (this *MovingAverage) Next(val int) float64 {
	if this.count == this.size {
		this.last_avg += float64((val - this.array[0])) / float64(this.count)
		this.array = append(this.array[1:], val)
	} else {
		this.array[this.count] = val
		this.count++
		this.last_avg += (float64(val) - this.last_avg) / float64(this.count)
	}
	return this.last_avg
}

//剑指 Offer II 027. 回文链表
func isPalindromeList(head *ListNode) bool {
	slow, fast := head, head
	for fast != nil {
		slow = slow.Next
		fast = fast.Next
		if fast != nil {
			fast = fast.Next
		}
	}
	var pre *ListNode
	temp:=slow
	for temp!=nil{
		x:=temp.Next
		temp.Next=pre
		pre=temp
		temp=x
	}
	n1,n2:=head,pre
	for n2!=nil{
		if n1.Val!=n2.Val{
			return false
		}
		n1=n1.Next
		n2=n2.Next
	}
	return true
}
